//https://leetcode.cn/problems/minimum-number-of-removals-to-make-mountain-array/submissions/490521112/?envType=daily-question&envId=2023-12-22


const int N = 1010;
class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        array<int, N> incr, decr;
        int q[N]{0};
        int len = 0;
        for (int i = 0; i < n; i ++)
        {
            int l = 0, r = len;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= nums[i]) l = mid;
                else r = mid - 1;
            }
            if (nums[i] != q[r]) ++ r;
            len = max(len, r);
            q[r] = nums[i];
            incr[i] = r;
        }
        int res = 0;
        len = 0;
        for (int i = n - 1; ~i; i --)
        {
            int l = 0, r = len;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= nums[i]) l = mid;
                else r = mid - 1;
            }

            if (nums[i] != q[r]) ++ r;
            len = max(len, r);
            q[r] = nums[i];
            if (r > 1 && incr[i] > 1) res = max(res, incr[i] + r - 1);
        }
        return n - res;
    }
};